package main.java.indi.zyj.coderecord;

import main.java.indi.zyj.hot100.base.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Rob3 {

    public int rob(TreeNode root) {
        int[] res = robTree(root);
        return Math.max(res[0], res[1]);
    }

    private int[] robTree(TreeNode root) {

        // 长度为2的数组，0：不偷，1：偷
        // 当前节点偷与不偷所得到的的最大金钱。
        int[] res = new int[2];

        if (root == null)
            return res;

        int[] left = robTree(root.left);
        int[] right = robTree(root.right);

        // 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
        // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
        //                      Math.max(rob(root.right)[0], rob(root.right)[1])
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
        // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
        res[1] = root.val + left[0] + right[0];

        return res;

    }


    // 必须是后序遍历方便判断节点状态
    public int[] rob1(TreeNode root) {

        // 0->偷  1->不偷
        int[] select = new int[2];

        if (root == null) {
            return select;
        }

        int[] left = rob1(root.left);
        int[] right = rob1(root.right);

        // 偷当前节点，左右接节点不偷
        select[0] = root.val + left[1] + right[1];

        // 不偷，左右接节点选取最大的选择去偷
        select[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return select;

    }


    // 1.递归去偷，超时
    public int rob2(TreeNode root) {
        if (root == null)
            return 0;
        int money = root.val;
        if (root.left != null) {
            money += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money, rob(root.left) + rob(root.right));
    }

    // 2.递归去偷，记录状态
    // 执行用时：3 ms , 在所有 Java 提交中击败了 56.24% 的用户
    public int rob3(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    int robAction(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null)
            return 0;
        if (memo.containsKey(root))
            return memo.get(root);
        int money = root.val;
        if (root.left != null) {
            money += robAction(root.left.left, memo) + robAction(root.left.right, memo);
        }
        if (root.right != null) {
            money += robAction(root.right.left, memo) + robAction(root.right.right, memo);
        }
        int res = Math.max(money, robAction(root.left, memo) + robAction(root.right, memo));
        memo.put(root, res);
        return res;
    }

}
